package DataStructureAndAlgorithm.CSP.Day02;
import java.util.*;
//无线网络
//宽搜图 + 宽搜插点法

//可以使用k个路由，即可以通过最多k个特殊点的最短路问题

//dp的分析方式，可以用最短路来解决
//dist[i][j]：表示到达第i个点，且恰好适用了j个新路由的最短路径长度

//
public class AcWing_3200 {
    static class pair{
        int x;
        int y;
        pair(int x,int y){
            this.x = x;
            this.y = y;
        }
    }


    static int N = 210;
    static int M = N * N;
    static int n,m,k,r;
    static int[] h = new int[N]; // 头结点
    static int[] e = new int[M]; // 存值
    static int[] ne = new int[M]; // 存链
    static int idx = 0;
    static pair[] p = new pair[N];
    //dist[i][j]：表示到达第i个点，且恰好适用了j个新路由的最短路径长度
    static int[][] dist = new int[N][N];


    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        k = in.nextInt();
        r = in.nextInt();

        //初始化所有头结点为-1
        Arrays.fill(h,-1);

        //读入已经存在的n个路由
        for (int i = 1; i <= n; i++) {
            int x = in.nextInt();
            int y = in.nextInt();
            p[i] = new pair(x,y);
        }
        //读入可以添加新路由的点
        for (int i = n + 1; i <= n + m; i++){
            int x = in.nextInt();
            int y = in.nextInt();
            p[i] = new pair(x,y);
        }
        //在所有已经读入的点之间建边(任意两个在r范围内的点都建边)
        for (int i = 1; i <= n + m; i++){
            for (int j = i + 1; j <= n + m; j++){
                if (check(p[i],p[j])){
                    //无向边，故建两条有向边
                    add(i,j);
                    add(j,i);
                }
            }
        }

        //宽搜出最短路径
        int res = bfs();
        System.out.print(res);
    }

    static boolean check (pair a,pair b){
        long dx = a.x - b.x;
        long dy = a.y - b.y;
        return dx * dx + dy * dy <= (long)r * r;
    }

    static void add(int a,int b){
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    static int bfs(){
        Queue<pair> queue = new LinkedList<>();
        queue.offer(new pair(1,0));
        for (int i = 0; i < N; i++){
            Arrays.fill(dist[i],99999999);
        }
        dist[1][0] = 0;

        while (!queue.isEmpty()){
            pair temp = queue.poll();
            for (int i = h[temp.x]; i != -1; i = ne[i]){
                int x = e[i];
                int y = temp.y;
                //判断x是否是特殊点(添加的新路由的点)
                if (x > n)y++;
                //判断是否已经用了所有的k个路由
                if (y <= k){
                    //判断是否可以更新路径
                    if (dist[x][y] > dist[temp.x][temp.y] + 1){
                        dist[x][y] = dist[temp.x][temp.y] + 1;
                        queue.offer(new pair(x,y));
                    }
                }
            }
        }

        //求出最短路径
        int res = 99999999;
        for (int i = 0; i <= k; i++){
            res = Math.min(res,dist[2][i]);
        }
        return res - 1;
    }
}

/*
目前在一个很大的平面房间里有 n

个无线路由器，每个无线路由器都固定在某个点上。

任何两个无线路由器只要距离不超过 r

就能互相建立网络连接。

除此以外，另有 m

个可以摆放无线路由器的位置。

你可以在这些位置中选择至多 k

个增设新的路由器。

你的目标是使得第 1
个路由器和第 2

个路由器之间的网络连接经过尽量少的中转路由器。

请问在最优方案下中转路由器的最少个数是多少?
输入格式

第一行包含四个正整数 n,m,k,r

。

接下来 n
行，每行包含两个整数 xi 和 yi，表示一个已经放置好的无线路由器在 (xi,yi) 点处。输入数据保证第 1 和第 2 个路由器在仅有这 n

个路由器的情况下已经可以互相连接(经过一系列的中转路由器)。

接下来 m
行，每行包含两个整数 xi 和 yi，表示 (xi,yi)

点处可以增设一个路由器。

输入中所有的坐标的绝对值不超过 108

，保证输入中的坐标各不相同。
输出格式

输出只有一个数，即在指定的位置中增设 k
个路由器后，从第 1 个路由器到第 2

个路由器最少经过的中转路由器的个数。
数据范围

2≤n≤100
,
1≤k≤m≤100,
1≤r≤108

输入样例：

5 3 1 3
0 0
5 5
0 3
0 5
3 5
3 3
4 4
3 0

输出样例：

2

 */